/**
* @file         
* @brief		单链表，无头结点.
* @details	    基本功能演示
* @author		conkty@126.com
* @date		    2023
* @version	    v0.1
* @par 更新记录:         
*	v0.1: 初建\n
*/

#include <stdlib.h>
#include <stdio.h>

typedef struct LNode {
    int data;
    struct LNode *next;
} Node, *LinkList;

// 追加新结点
int append(LinkList* plist, int value) {
    printf("info: appending %d ...\n", value);
    // 为新元素分配结点
    Node* newp = (Node *)malloc(sizeof(Node));
    newp->data = value;
    newp->next = NULL;

    if(NULL == *plist) // 空表，直接作为首结点
        *plist = newp;
    else { // 非空，放尾部
        Node *p = *plist;
        while(NULL != p->next)
            p = p->next;
        p->next = newp;
    }
        
    return 0;
}

// 新增结点在任意位置
int add(LinkList* plist, int value, int pos) {
    printf("info: adding %d to %d ...\n", value, pos);
    // 要判断pos的合法性或强制改为合法.
    if (pos < 0 ) {
        printf("warn: negtive pos, be forced to 0.\n");
        pos = 0;
    }

    Node *p = *plist; // 取表头
    int i = 0;

    // 为新元素分配结点
    Node* newp = (Node *)malloc(sizeof(Node));
    newp->data = value;
    // 对插入首部做特殊处理
    if(0 == pos) {
        *plist = newp;
        newp->next = p;
        return 0;
    }

    // 移动到指定位置的前一结点
    while(NULL != p && i < (pos-1)) {
        printf("info: moved to %d ...\n", i);
        p = p->next; // 不断后移
        ++i;
    }

    // 修改前驱后继关系
    newp->next = p->next;
    p->next = newp;

    return 0;
}

// 移除指定位置结点
int delete(LinkList* plist, int pos) {
    // 要求: pos是从0开始的整数
    printf("info: removing node at %d ...\n", pos);
    if (pos < 0 ) {
        printf("warn: invalid pos.\n");
        return -1;
    }

    Node *p = *plist; // 取表头
    int i = 0;

    // 首结点特殊处理
    if(0 == pos) {
        *plist = p->next;
        printf("removing: %p\n", p);
        free(p);
        return 0;
    }

    // 移动到指定位置的前一结点
    while(NULL != p->next && i < (pos-1)) {
        printf("info: moved to %d ...\n", i);
        p = p->next; // 不断后移
        ++i;
    }
    // 此时, p应指向指定结点的直接前驱
    // 但当pos为0时，p此时指向首结点，而非头指针
    // 故应对首结点做特殊处理

    // 待删除结点
    Node * q = p->next;
    // p后继改为指定结点的后继
    p->next = q->next;
    // 销毁指定结点
    printf("removing: %p\n", q);
    free(q);

    return 0;
}

// 遍历，打印每个元素
void traverse(LinkList list) {
    Node *p = list; // 取表头
    while (NULL != p) {
        printf("addr: %p, cell: %d, next: %p\n", p, p->data, p->next);
        p = p->next; // 不断后移
    }
}

// 销毁占用空间
void destroy(LinkList list) {
    Node *p = list;
    while (NULL != p) {
        // 先记录后继结点地址
        Node * next_bak = p->next;
        // 销毁当前结点
        printf("destroying: %p\n", p);
        free(p);
        p = next_bak;
    }
}

int main()
{

    LinkList list = NULL;
    append(&list, 12);
    append(&list, 13);
    append(&list, 14);
    traverse(list);
/*
    delete(&list, 0);
    traverse(list);
*/
    add(&list, 21, 1);
    traverse(list);

    destroy(list);
    return 0;
}